\subsection{谱聚类}

关于谱聚类我看的文献是 \cite{2004A}, 这个在 Springer 上有 5982 次引用, 是一篇总结谱聚类很好的文章, 接下来对这篇文章做一个小梳理

\subsubsection{基础定义定理}

\begin{defn}[邻接矩阵, 度]
    Let $G=\left( V,E \right)$ be an undireccted graph with vertex set $V=\left\{ v_1,v_2,\cdots,v_n \right\}$ .
    In the following we assume that the graph $G$ is weighted, that is each edge between two vetices $v_1$ and $v_j$ 
    carries a non-negative weight $w_{ij}\ge 0$ . The weighted adjacency maatrix of the graph is the matrix $W=\left( w_{ij} \right)_{n\times n}$.
    If $w_{ij}=0$ this means that the vertices $v_i$ and $v_j$ are not connected by an edge. As $G$ is undirected we require $w_{ij}=w_{ji}$ .
    The degree of a vertex $v_i\in V$ defined as 
    $$ d_i=\sum_{j=1}^nw_{ij} $$
\end{defn}

\begin{defn}[指示向量]
    Given a subset of vertices $A\subset V$ , we denote its complement $V\\ A$ by $\bar{A}$ . We define the indicator vector 
    $$ \vmathbb{1}_A=\left( f_1,f_2,\cdots,f_n \right)'\in \mathbb{R}^n $$
    and
    $$ f_i=\begin{cases}
        1 & i\in A \\ 
        0 & otherwise. 
    \end{cases} $$
\end{defn}

\begin{defn}[子集间的权重]
    For two necessarily disjoint sets $A,B\subset V$ we define 
    $$ W(A,B) = \sum_{i\in A,j\in B}w_{ij} $$  
\end{defn}

\begin{defn}[连通图]
    A subset $A$ of a graph is connected if any two vertices in $A$ can be joined by a path such that all internediate points also lie in $A$.
\end{defn}

\begin{defn}[连通分支]
    A subset $A$ is called a connected component if it is connected and if there are no connections between vertices in $A$ and $\bar{A}$. 
    The nonempty sets $A_1,A_2,\cdots,A_k$ form a partition of the graph if $A_i\bigcap A_j=\varnothing$ and $\bigcup_{i=1}^k A_i = V$.  
\end{defn}


\begin{defn}[子集的度量]
    We consider two different ways of measuring the ``size'' of a subset $A\subset V$:
    $$ \begin{gathered}
        |A| = \text{the number of vertices in } A \\ 
        \mathrm{vol}(A) = \sum_{i\in A}d_i.
    \end{gathered} $$
\end{defn}

\subsubsection{不同的相似图(邻接矩阵的构造)}

这一节主要讲了如何构造邻接矩阵, 也就是图如何去连接. 分三种方法

\begin{itemize}
    \item $\varepsilon$ 邻域图;
    \item $k$ 近邻图;
    \item 全链接图
\end{itemize}

看名字都很好猜定义是什么样的. 不展开说明, 只说明一点: 前两种图都是不加权的(权重只有0和1), 第三种是加权图(权重不一定是0或1, 是非负实数就可以).


\subsubsection{Laplace 算子}
Laplace 算子分两种: 非归一的和归一的, 首先介绍非归一的

\begin{defn}[Laplace 算子]
    图 $G=\left( V,E \right)$ 中, $D=\mathrm{diag}(d_1,d_2,\cdots,d_n)$, $W=\left( w_{ij} \right)_{n\times n}$.  
    $$ L=D-W $$
    称为 Laplace 算子.
\end{defn}

\begin{pro}
    对于拉普拉斯算子 $L=D-W$ 有以下性质:
    \begin{itemize}
        \item $\forall f\in \mathbb{R}^n, f'Lf=\frac{1}{2}\sum_{i,j=1}^{n}w_{ij}(f_i-f_j)^2$ ;
        \item $L$ is symmetric and positive semi-definite;
        \item The smallest eigenvalue of $L$ is $0$ ,the corresponding eigenvector is the constant one vactor $\vmathbb{1}$.
        \item $L$ has $n$ non-negative,real-valued eigenvalues $0=\lambda_1\le\lambda_2\le\cdots\le\lambda_n$ .
    \end{itemize}
\end{pro}

\begin{pro}[$L$ 的连通分支和谱]
    Let $G$ be an undirected graph with non-negative weights. Then the multiplicity $k$ of the eigenvalue $0$ of $L$ equals the number of connected components
    $A_1,\cdots,A_k$ in the graph. The eigenspace of eigenvalue $0$ is spanned by the indicator vectors $\vmathbb{1}_{A_1},\cdots,\vmathbb{1}_{A_k}$ of those components.
\end{pro}

接下来是归一的 
\begin{defn}[Laplace 算子]
    $$ \begin{gathered}
        L_{sym} = D^{-\frac{1}{2}}LD^{-\frac{1}{2}} = I - D^{-\frac{1}{2}}WD^{-\frac{1}{2}}\\ 
        L_{rm} = D^{-1}L = I-D^{-1}W.
    \end{gathered} $$
\end{defn}



\subsubsection{谱聚类}

图是由很多边连接的, 我们想达到聚类的目的就要``切断'' 某些边, 使得异类之间的权重小, 同类之间的权重大. 所以 $W(A_i,A_j)$ 就使我们要关注的东西.

构造图的划分最简单、最直接的方法就是求解mincut问题.对于给定数量 $k$ 的子集，mincut方法简单地包括选择最小化的分区$A_1，\cdots，A_k$.

$$ \mathrm{cut}(A_1,\cdots,A_k)=\frac{1}{2}\sum_{i=1}^{k}W(A_i,\bar{A_i}) $$
然而，在实践中，它通常不会导致令人满意的分区.问题是，在许多情况下,mincut的解决方案只是将一个单独的顶点与图的其余部分分开.
所以我们要加上一些``限制''使其不让他把一个单独的点分开, 显然我们要让 $\mathrm{cut}(A_1,\cdots,A_k)$ 最小, 但是要让每个分区的顶点尽量多, 所以我们改进一下表达式,
加上对顶点 $A$ 的度量就变成了 RatioCut 和 NCut问题:

RatioCut:
$$ \begin{aligned}
    \mathrm{RatioCut}(A_1,\cdots,A_k)&=\frac{1}{2}\sum_{i=1}^{k}\frac{W(A_i,\bar{A_i})}{|A_i|} \\ 
    &= \sum_{i=1}^{k}\frac{\mathrm{Cut}(A_i,\bar{A_i})}{|A_i|}
\end{aligned}$$

NCut:
$$ \begin{aligned}
    \mathrm{NCut}(A_1,\cdots,A_k)&=\frac{1}{2} \sum_{i=1}^{k}\frac{W(A_i,\bar{A_i})}{vol(A_i)}\\ 
    &= \sum_{i=1}^{k}\frac{\mathrm{Cut}(A_i,\bar{A_i})}{vol(A_i)}
\end{aligned} $$

所以我们的问题就转换成了一个规划问题:使这两种 Cut 极小化.

\subsubsection{优化目标函数}
在 RatioCut 问题中,我们改进一下指示向量:

\begin{defn}[改进的指示向量]
    Given a partition of $V$ into $k$ sets $A_1,\cdots,A_k$ ,we define $k$ indicator vectors $h_j=\left( h_{1j},\cdots,h_{nj} \right)'$ by
    $$ h_{ij}=\begin{cases}
        \frac{1}{\sqrt{|A_j|}} & v_i\in A_j \\ 
        0 & otherwise. 
    \end{cases} $$
\end{defn}

接下来令 $H=\left( h_1,h_2,\cdots,h_k \right)$ 是一个 $n\times k$ 的矩阵, 我们发现一个性质 $HH^T=I$, 我们注意到 
$$ h_i'Lh_i=\frac{\mathrm{cut}(A_i,\bar{A_i})}{|A_i|}. $$ 

而且 
$$ h_i'Lh_i = (H'LH)_{ii} $$
所以可以将 RatioCut 的问题转化为:
$$ \mathrm{RatioCut}(A_1,\cdots,A_k)=\sum_{i=1}^k h_i'Lh_i = \sum_{i=1}^k(H'LH)_{ii}=Tr(H'LH) $$
最小化 RatioCut 的问题就转化为:
$$ \min_{A_1,\cdots,A_k}\mathrm{RatioCut}(A_1,\cdots,A_k)=\min_{A_1,\cdots,A_k}Tr(H'LH) $$
使得 
$$ H'H=I $$

但是, 这很难解, 因为 $h_i$ 有 $2^n$ 种可能, $H$ 就有 $2^nk$ 种可能, 所以这是一个 NP 难问题!

如果我们观察 $Tr(H'LH)$ 中的每一个优化子目标 $h_i'Lh_i$ ,其中 $h$ 是单位正交基, $L$ 是对称矩阵.
此时 $h_i'Lh_i$ 的最大值就是 $L$ 的最大特征值, 最小值就是 $L$ 的最小特征值. 所以我们就要找到 $L$ 的
 $k$ 个最小的特征值, 得到对应的特征向量 $\left\{ v_1,v_2,\cdots,v_k \right\}$ . 用这 $k$ 个向量组成的矩阵就是我们要的 $H$.  
 这个解法参考书为 \cite{Helmut1996Handbook} 的 5.2.2.(6)


在 NCut 问题中, 我们也改进一下指示向量:

\begin{defn}[改进的指示向量]
    Given a partition of $V$ into $k$ sets $A_1,\cdots,A_k$ ,we define $k$ indicator vectors $h_j=\left( h_{1j},\cdots,h_{nj} \right)'$ by
    $$ h_{ij}=\begin{cases}
        \frac{1}{\sqrt{vol(A_j)}} & v_i\in A_j \\ 
        0 & otherwise. 
    \end{cases} $$
\end{defn}

像 RatioCut 问题一样, 我们也可以将 NCut 问题变成一个规划问题:
$$ \min_{A_1,\cdots,A_k}Tr(H'LH)   $$
使得 
$$ H'DH=I $$
但是这样的话 $H$ 就不是正交矩阵了, 所以我们改造一下: 令 $T=D^{\frac{1}{2}}H$ 所以就变为了
$$ \min_{A_1,\cdots,A_k}Tr(T'D^{-\frac{1}{2}}LD^{-\frac{1}{2}}T)  $$
使得 
$$ T'T=I $$


最后得到的矩阵 $H$ 或者 $T$ 会有一些损失, 所以其中的列向量不一定就是我们要的指示向量而是逼近指示向量. 所以我们对 $H$ 或者 $T$ 的列向量 $y_i$ 做 K-Means 聚类, 
就会得到 $\left\{ C_1,C_2,\cdots,C_k \right\}$ , 然后得到最后的结果 
$$ A_i=\left\{ j\Big|y_j\in C_i \right\} $$